package exer1;

/**
 * @author tongchen
 * @create 2022-10-09 17:39
 */
public class ListNode {
    int val;

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }

    ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(4);
list1.next=listNode1;
listNode1.next=listNode2;
        ListNode list2 = new ListNode(1);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        list2.next=listNode3;
        listNode3.next=listNode4;
        System.out.println(Solution.mergeTwoLists(list1, list2));
    }
}
class Solution {
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //设置两个中间结点
        ListNode temp1=list1;
        ListNode temp2=list2;
        //设置头结点，用于循环遍历
        ListNode head=list1.val>list2.val?list2:list1;
        if (head==list1){
            temp1=temp1.next;
        }
        else{
            temp2=temp2.next;
        }
        ListNode cur=head;
        while(temp1!=null&&temp2!=null){
            cur.next=temp1.val>temp2.val?temp2:temp1;
            if(cur.next==temp1){
                temp1=temp1.next;
            }
            else{
                temp2=temp2.next;
            }
            cur=cur.next;
        }
        //将剩余部分进行拼接
        while(temp1!=null){
            cur.next=temp1;
            cur=cur.next;
            temp1=temp1.next;
        }
        while(temp2!=null){
            cur.next=temp2;
            cur=cur.next;
            temp2=temp2.next;
        }
        return head;
    }
}
